<!DOCTYPE html><html lang="zh-Hans" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>算法笔记 | DreamcatcherDENG 的个人博客</title><meta name="author" content="dreamcatcherdeng"><meta name="copyright" content="dreamcatcherdeng"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="referrer" content="no-referrer"><meta name="description" content="本文介绍了算法中常见的知识点和技巧，代码使用伪码或c++实现">
<meta property="og:type" content="article">
<meta property="og:title" content="算法笔记">
<meta property="og:url" content="https://dreamcatcherdeng.github.io/personal-blog/2022/07/13/Algorithm/index.html">
<meta property="og:site_name" content="DreamcatcherDENG 的个人博客">
<meta property="og:description" content="本文介绍了算法中常见的知识点和技巧，代码使用伪码或c++实现">
<meta property="og:locale">
<meta property="og:image" content="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-e7ek7k.jpg">
<meta property="article:published_time" content="2022-07-13T09:38:00.841Z">
<meta property="article:modified_time" content="2022-07-16T16:23:33.220Z">
<meta property="article:author" content="dreamcatcherdeng">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-e7ek7k.jpg"><link rel="shortcut icon" href="/personal-blog/img/favicon.png"><link rel="canonical" href="https://dreamcatcherdeng.github.io/personal-blog/2022/07/13/Algorithm/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/personal-blog/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@6/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/personal-blog/',
  algolia: undefined,
  localSearch: {"path":"search.xml","languages":{"hits_empty":"We didn't find any results for the search: ${query}"}},
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: 'Copy successfully',
    error: 'Copy error',
    noSupport: 'The browser does not support'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '',
  date_suffix: {
    just: 'Just',
    min: 'minutes ago',
    hour: 'hours ago',
    day: 'days ago',
    month: 'months ago'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '算法笔记',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2022-07-17 00:23:33'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end --><meta name="generator" content="Hexo 5.4.2"><link rel="alternate" href="/personal-blog/atom.xml" title="DreamcatcherDENG 的个人博客" type="application/atom+xml">
</head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://n.sinaimg.cn/sinakd10100/452/w1080h972/20200416/93dc-iskepxs3894040.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data is-center"><div class="data-item"><a href="/personal-blog/archives/"><div class="headline">Articles</div><div class="length-num">34</div></a></div><div class="data-item"><a href="/personal-blog/tags/"><div class="headline">Tags</div><div class="length-num">0</div></a></div><div class="data-item"><a href="/personal-blog/categories/"><div class="headline">Categories</div><div class="length-num">35</div></a></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/personal-blog/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/personal-blog/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/personal-blog/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div><div class="menus_item"><a class="site-page" href="/personal-blog/about/"><i class="fa-fw fas fa-heart"></i><span> About</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-e7ek7k.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/personal-blog/">DreamcatcherDENG 的个人博客</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> Search</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/personal-blog/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/personal-blog/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/personal-blog/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div><div class="menus_item"><a class="site-page" href="/personal-blog/about/"><i class="fa-fw fas fa-heart"></i><span> About</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">算法笔记</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">Created</span><time class="post-meta-date-created" datetime="2022-07-13T09:38:00.841Z" title="Created 2022-07-13 17:38:00">2022-07-13</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">Updated</span><time class="post-meta-date-updated" datetime="2022-07-16T16:23:33.220Z" title="Updated 2022-07-17 00:23:33">2022-07-17</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/personal-blog/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">Word count:</span><span class="word-count">1.2k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">Reading time:</span><span>6min</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="算法笔记"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">Post View:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><blockquote>
<p>本文介绍了算法中常见的知识点和技巧，代码使用伪码或c++实现</p>
</blockquote>
 <span id="more"></span>
<hr>
<h1 id="数据类型"><a href="#数据类型" class="headerlink" title="数据类型"></a>数据类型</h1><ul>
<li>字符型<ul>
<li>字符 </li>
<li>字符串 </li>
</ul>
</li>
<li>数字型<ul>
<li>整型</li>
<li>浮点型</li>
</ul>
</li>
<li>bool型<ul>
<li>bool值<br><details><summary>数据类型取值范围表 </summary>

</li>
</ul>
</li>
</ul>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:left">类型</th>
<th style="text-align:left">位</th>
<th style="text-align:left">范围</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:left">char</td>
<td style="text-align:left">1 个字节</td>
<td style="text-align:left">-128 到 127 或者 0 到 255</td>
</tr>
<tr>
<td style="text-align:left">unsigned char</td>
<td style="text-align:left">1 个字节</td>
<td style="text-align:left">0 到 255</td>
</tr>
<tr>
<td style="text-align:left">signed char</td>
<td style="text-align:left">1 个字节</td>
<td style="text-align:left">-128 到 127</td>
</tr>
<tr>
<td style="text-align:left">int</td>
<td style="text-align:left">4 个字节</td>
<td style="text-align:left">-2147483648 到 2147483647</td>
</tr>
<tr>
<td style="text-align:left">unsigned int</td>
<td style="text-align:left">4 个字节</td>
<td style="text-align:left">0 到 4294967295</td>
</tr>
<tr>
<td style="text-align:left">signed int</td>
<td style="text-align:left">4 个字节</td>
<td style="text-align:left">-2147483648 到 2147483647</td>
</tr>
<tr>
<td style="text-align:left">short int</td>
<td style="text-align:left">2 个字节</td>
<td style="text-align:left">-32768 到 32767</td>
</tr>
<tr>
<td style="text-align:left">unsigned short int</td>
<td style="text-align:left">2 个字节</td>
<td style="text-align:left">0 到 65,535</td>
</tr>
<tr>
<td style="text-align:left">signed short int</td>
<td style="text-align:left">2 个字节</td>
<td style="text-align:left">-32768 到 32767</td>
</tr>
<tr>
<td style="text-align:left">long int</td>
<td style="text-align:left">8 个字节</td>
<td style="text-align:left">-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807</td>
</tr>
<tr>
<td style="text-align:left">signed long int</td>
<td style="text-align:left">8 个字节</td>
<td style="text-align:left">-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807</td>
</tr>
<tr>
<td style="text-align:left">unsigned long int</td>
<td style="text-align:left">8 个字节</td>
<td style="text-align:left">0 到 18,446,744,073,709,551,615</td>
</tr>
<tr>
<td style="text-align:left">float</td>
<td style="text-align:left">4 个字节</td>
<td style="text-align:left">精度型占4个字节（32位）内存空间，+/- 3.4e +/- 38 (~7 个数字)</td>
</tr>
<tr>
<td style="text-align:left">double</td>
<td style="text-align:left">8 个字节</td>
<td style="text-align:left">双精度型占8 个字节（64位）内存空间，+/- 1.7e +/- 308 (~15 个数字)</td>
</tr>
<tr>
<td style="text-align:left">long double</td>
<td style="text-align:left">16 个字节</td>
<td style="text-align:left">长双精度型 16 个字节（128位）内存空间，可提供18-19位有效数字。</td>
</tr>
<tr>
<td style="text-align:left">wchar_t</td>
<td style="text-align:left">2 或 4 个字节</td>
<td style="text-align:left">1 个宽字符</td>
</tr>
</tbody>
</table>
</div>
<p>&lt;/details&gt;</p>
<h1 id="符号定义"><a href="#符号定义" class="headerlink" title="符号定义"></a>符号定义</h1><div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">数学符号</th>
<th style="text-align:left">定义</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">$\pi$</td>
<td style="text-align:left"><code>#define P acos(-1.0)</code></td>
</tr>
<tr>
<td style="text-align:center">$\varepsilon$</td>
<td style="text-align:left"><code>#define eps 1e-8</code></td>
</tr>
<tr>
<td style="text-align:center">$+\infty$</td>
<td style="text-align:left"><code>INF</code></td>
</tr>
</tbody>
</table>
</div>
<blockquote>
<p>对于<code>unsigned int</code>型<code>#define INF 0xffffffff</code>，对于<code>int</code>型<code>#define INF 0x7fffffff</code>，一般的问题 <code>#define INF 0x3f3f3f3f</code></p>
</blockquote>
<h1 id="函数定义"><a href="#函数定义" class="headerlink" title="函数定义"></a>函数定义</h1><h2 id="浮点数的比较"><a href="#浮点数的比较" class="headerlink" title="浮点数的比较"></a>浮点数的比较</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="comment">//等于</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">equal</span><span class="params">(<span class="keyword">double</span> a,<span class="keyword">double</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">fabs</span>(a-b) &lt; eps;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//大于</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">more</span><span class="params">(<span class="keyword">double</span> a,<span class="keyword">double</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (a-b) &gt; eps;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//小于</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">less</span><span class="params">(<span class="keyword">double</span> a,<span class="keyword">double</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (a-b) &lt; (-eps);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//大于等于</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">more_equal</span><span class="params">(<span class="keyword">double</span> a,<span class="keyword">double</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (a-b) &gt; (-eps);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//小于等于</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">less_equal</span><span class="params">(<span class="keyword">double</span> a,<span class="keyword">double</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (a-b) &lt; eps;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="获取数组的长度"><a href="#获取数组的长度" class="headerlink" title="获取数组的长度"></a>获取数组的长度</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> get_length(array) (sizeof(array) / sizeof(array[0]))</span></span><br></pre></td></tr></table></figure>
<h1 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h1><blockquote>
<p>注:排序算法，默认按升序排</p>
<h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><p><img src="http://124.221.123.212:8080/images/bubbleSort-1630041514436.gif" alt="冒泡排序"></p>
</blockquote>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//冒泡排序</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">bubble_sort</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;array)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = array.<span class="built_in">size</span>();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = length;i &gt;= <span class="number">0</span>;--i)&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; i; ++j) &#123;</span><br><span class="line">            <span class="keyword">if</span> (array[j<span class="number">-1</span>] &gt; array[j])&#123;</span><br><span class="line">                <span class="built_in">swap</span>(array[j<span class="number">-1</span>],array[j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="简单选择排序"><a href="#简单选择排序" class="headerlink" title="简单选择排序"></a>简单选择排序</h2><p><img src="http://124.221.123.212:8080/images/selectionSort-1630041521071.gif" alt="选择排序"><br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//选择排序</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">select_sort</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;array)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = array.<span class="built_in">size</span>();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; length - <span class="number">1</span>;++i)&#123;</span><br><span class="line">        <span class="keyword">int</span> min = i;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i+<span class="number">1</span>; j &lt; i; ++j) &#123;</span><br><span class="line">            <span class="keyword">if</span> (array[i] &gt; array[j])</span><br><span class="line">            &#123;</span><br><span class="line">                min = j;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">swap</span>(array[i],array[min]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><p><img src="http://124.221.123.212:8080/images/8082826-efd1067c85cd0a95.gif" alt="img"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//插入排序</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insert_sort</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;array)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = array.<span class="built_in">size</span>();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>;i &lt; length;++i)&#123;</span><br><span class="line">        <span class="keyword">int</span> current = array[i];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j = i<span class="number">-1</span>;j &gt;= <span class="number">0</span>;--j)&#123;</span><br><span class="line">            <span class="keyword">if</span>(array[j] &gt; current)&#123;</span><br><span class="line">                array[j+<span class="number">1</span>] = array[j];</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                array[j+<span class="number">1</span>] = current;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//归并排序</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;arr,<span class="keyword">int</span> left,<span class="keyword">int</span> mid,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i = left,j = mid+<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> k = <span class="number">0</span>;</span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">temp</span><span class="params">(right-left+<span class="number">1</span>)</span></span>;</span><br><span class="line">    <span class="keyword">while</span> ((i &lt;= mid) &amp;&amp; (j &lt;= right))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(arr[i] &lt;= arr[j])&#123;</span><br><span class="line">            temp[k++] = arr[i++];</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            temp[k++] = arr[j++];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">while</span>(j &lt;= right)&#123;</span><br><span class="line">        temp[k++] = arr[j++];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(i &lt;= mid)&#123;</span><br><span class="line">        temp[k++] = arr[i++];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(k &gt; <span class="number">0</span>)&#123;</span><br><span class="line">        arr[--j] = temp[--k];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge_sort</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;arr,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left &lt; right)&#123;</span><br><span class="line">        <span class="keyword">int</span> mid = left + (right-left)/<span class="number">2</span>;</span><br><span class="line">        <span class="built_in">merge_sort</span>(arr,left,mid);</span><br><span class="line">        <span class="built_in">merge_sort</span>(arr,mid+<span class="number">1</span>,right);</span><br><span class="line">        <span class="built_in">merge</span>(arr,left,mid,right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><p><img src="http://124.221.123.212:8080/images/8082826-baea8ca0324958f9.gif" alt="img"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">partition</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;arr,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i = left,j= right + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> temp = arr[i];</span><br><span class="line">    <span class="keyword">while</span>(<span class="literal">true</span>)&#123;</span><br><span class="line">        <span class="keyword">while</span>(arr[++i] &lt; temp &amp;&amp; i &lt; right);</span><br><span class="line">        <span class="keyword">while</span>(temp &lt; arr[--j]);</span><br><span class="line">        <span class="keyword">if</span>(i &gt;= j)&#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">swap</span>(arr[i],arr[j]);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    arr[left] = arr[j];</span><br><span class="line">    arr[j] = temp;</span><br><span class="line">    <span class="keyword">return</span> j;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span>  <span class="title">quick_sort</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;arr,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left &lt; right)&#123;</span><br><span class="line">        <span class="keyword">int</span> base = <span class="built_in">partition</span>(arr,left,right);</span><br><span class="line">        <span class="built_in">quick_sort</span>(arr,left,base<span class="number">-1</span>);</span><br><span class="line">        <span class="built_in">quick_sort</span>(arr,base+<span class="number">1</span>,right); </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">graph TD</span><br><span class="line">1--&gt;2</span><br><span class="line">1--&gt;3</span><br><span class="line">2--&gt;4</span><br><span class="line">2--&gt;5</span><br><span class="line">3--&gt;6</span><br><span class="line">3--&gt;7</span><br><span class="line">4--&gt;8</span><br><span class="line">4--&gt;9</span><br><span class="line">5--&gt;10</span><br><span class="line">5--&gt;11</span><br><span class="line">6--&gt;12</span><br><span class="line">6--&gt;13</span><br><span class="line">7--&gt;14</span><br><span class="line">7--&gt;15</span><br></pre></td></tr></table></figure>
<h2 id="桶排序"><a href="#桶排序" class="headerlink" title="桶排序"></a>桶排序</h2><h2 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h2><h2 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h2><h1 id="递归"><a href="#递归" class="headerlink" title="递归"></a>递归</h1><h1 id="贪心"><a href="#贪心" class="headerlink" title="贪心"></a>贪心</h1><h1 id="二分法"><a href="#二分法" class="headerlink" title="二分法"></a>二分法</h1><h2 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//查找x在有序数组arr中的索引，若不存在返回-1</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">binary_search</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; arr,<span class="keyword">int</span> x,<span class="keyword">int</span> length)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> right = length<span class="number">-1</span>;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right)&#123;</span><br><span class="line">        <span class="keyword">int</span> mid = (left + right)/<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">if</span>(arr[mid] &lt; x)&#123;</span><br><span class="line">            left = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(arr[mid] &gt; x)&#123;</span><br><span class="line">            right = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="二分法求近似值"><a href="#二分法求近似值" class="headerlink" title="二分法求近似值"></a>二分法求近似值</h2><p>$f(x) = x^3+x^2-4$， 求$f(x)=0$的近似解</p>
<p><img src="http://124.221.123.212:8080/images/image-20210827200211194.png" alt="image-20210827200211194"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">f</span><span class="params">(<span class="keyword">double</span> x)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x*x*x + x*x - <span class="number">4</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">solve</span><span class="params">(<span class="keyword">double</span> left,<span class="keyword">double</span> right)</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">double</span> mid = left+(right-left)/<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">equal</span>(<span class="built_in">f</span>(mid),<span class="number">0.0</span>))&#123;</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">more</span>(<span class="built_in">f</span>(mid),<span class="number">0.0</span>))&#123;</span><br><span class="line">            right = mid;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            left = mid;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="快速幂"><a href="#快速幂" class="headerlink" title="快速幂"></a>快速幂</h1><h2 id="整数快速幂"><a href="#整数快速幂" class="headerlink" title="整数快速幂"></a>整数快速幂</h2><p>对于任意的数$x$，都可以通过位运算将它化为多个2的幂的和的形式。<br>例如:</p>
<script type="math/tex; mode=display">
    100_{10} = 1100100_{2} = 2^2+2^5+2^6 \\
    753_{10} = 1011110001_2 = 2^9+2^7+2^6+2^5+2^4+2^0</script><p>显然对于$2^n$，我们可以通过移位运算快速求得</p>
<script type="math/tex; mode=display">
2^n = 1<<n</script><p>当指数很大时，例如:$x^{753}$,再计算机中要表示成$753$个$x$相乘的形式,要进行752次乘法运算:</p>
<script type="math/tex; mode=display">
 \begin{array}{c}
      x^{753}=\underbrace{x  \cdot  x \cdots x \cdot x}_{753}
\end{array}</script><p>因为每次$x^n$计算的结果可以迭代成为下一次的结果$x^{2n}$，只需要做9次乘法运算</p>
<script type="math/tex; mode=display">
\begin{align}
    x^1 &= x \\
    x^2 &= (x^1）^2  \\
    x^4 &= (x^{2})^2 \\
    x^{8}  &= (x^4)^2 \\
    x^{16} &=(x^{8})^2    \\
    x^{32} &= (x^{16})^2  \\
    x^{64} &=(x^{32})^2    \\
    x^{128} &=(x^{64})^2    \\
    x^{256} &=(x^{128})^2    \\
    x^{512} &=(x^{256})^2
\end{align}</script><p>又因为$x^{735}$可以表示为:</p>
<script type="math/tex; mode=display">
x^{735} = x^{2^9+2^7+2^6+2^5+2^4+2^0}=x^{512}+x^{128}+x^{64}+x^{32}+x^{16}+x^1</script><p>则只需要做5次加法运算。</p>
<p>可以通过位运算求得x在第0，4，5，6，7，9次位运算时做加法运算，因此需要9次位运算。</p>
<script type="math/tex; mode=display">
  753_{10} = 1011110001_2 = 2^9+2^7+2^6+2^5+2^4+2^0\\</script><p>总共需要9次乘法运算，9次位运算，5次加法运算</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//快速幂代码是实现:</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">quick_power</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> N)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> base = x;</span><br><span class="line">    <span class="keyword">int</span> result = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(N)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(N&amp;<span class="number">1</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            result *= base;</span><br><span class="line">        &#125;</span><br><span class="line">        base *= base;</span><br><span class="line">        N = N&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="矩阵"><a href="#矩阵" class="headerlink" title="矩阵"></a>矩阵</h1><p>定义 $Matrix$ 为 $row \times col$ 的矩阵.<br>矩阵乘法:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">Matrix <span class="title">mul</span><span class="params">(Matrix A,Matrix B)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> N = A.row;</span><br><span class="line">    <span class="keyword">int</span> L = A.col;</span><br><span class="line">    <span class="keyword">int</span> M = B.col;</span><br><span class="line">    Matrix result = <span class="keyword">new</span> <span class="built_in">Matrix</span>(N,M);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; N;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j = <span class="number">0</span>;j &lt; L;j++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> k = <span class="number">0</span>;k &lt; M;k++)</span><br><span class="line">            	result[i][j] += A[i][k] * B[k][j];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="矩阵快速幂"><a href="#矩阵快速幂" class="headerlink" title="矩阵快速幂"></a>矩阵快速幂</h1><p>定义 $SquareMatrix$ 为 $n \times n$ 的方阵<br>对于一个方阵 A ,它的n次幂为：</p>
<script type="math/tex; mode=display">
A^n=\prod_{i=1}^n{A}</script><p>用递归代码:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">SquareMatrix <span class="title">matrixPower</span><span class="params">(SquareMatrix A,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(n == <span class="number">1</span>)&#123;</span><br><span class="line">		<span class="keyword">return</span> A;</span><br><span class="line">	&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">mul</span>(<span class="built_in">matrix_power</span>(A,N<span class="number">-1</span>),A);     </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>非递归代码:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">SquareMatrix <span class="title">matrixPower</span><span class="params">(SquareMatrix A,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    Square_Matrix result = <span class="keyword">new</span> <span class="built_in">Square_Matrix</span>(A);</span><br><span class="line">    <span class="keyword">int</span> N = A.row;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; N;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j = <span class="number">0</span>;j &lt; N;j++)&#123;</span><br><span class="line">            result[i][j] = A[i][j];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">   </span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; n<span class="number">-1</span>;i++)&#123;</span><br><span class="line">        result = <span class="built_in">mul</span>(result,A);</span><br><span class="line">    &#125;</span><br><span class="line">	<span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>对于$A^n$，需要做n-1次乘法运算。由整数快速幂的计算方法，你可能已经想到了，方阵也可以简化运算。没错，这就是矩阵快速幂。</p>
<p>如$A^{19}$次方:</p>
<script type="math/tex; mode=display">
A^{19} = A^{16} + A^2 + A^1</script><p>同样后面的运算结果可以由前面的运算结果迭代而来:</p>
<script type="math/tex; mode=display">
A^1</script><script type="math/tex; mode=display">
A^2 = A^1 * A^1</script><script type="math/tex; mode=display">
A^4 = A^2 * A^2</script><script type="math/tex; mode=display">
A^8 = A^4 * A^4</script><script type="math/tex; mode=display">
A^{16}=A^8*A^8</script><p>运算过程和整数快速幂相同，而两个矩阵的乘法运算上面已经有代码了</p>
<p>下面是矩阵快速幂代码</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">SquareMatrix <span class="title">matrixQuickPower</span><span class="params">(SquareMatrix A,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    SquareMatrix base = A;</span><br><span class="line">    SquareMatrix result;</span><br><span class="line">    <span class="comment">//对B进行初始化，初始化为单位阵</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; N;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j = <span class="number">0</span>;j &lt; N;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(i == j)&#123;</span><br><span class="line">                result[i][j] = <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                result[i][j] = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(n)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(n&amp;<span class="number">1</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            result = <span class="built_in">mul</span>(result,base);</span><br><span class="line">        &#125;</span><br><span class="line">        base = <span class="built_in">mul</span>(base,base);</span><br><span class="line">        n = n&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>矩阵快速幂的运用:</p>
<p>对于数列1,1,2,3,5……求其第$10^8$项。</p>
<p>记$f(0)=0,f(1) = 1$,对于该数列，易得：</p>
<script type="math/tex; mode=display">
\begin{align}
f(n)=1*f(n-1)+1*f(n-2)\\
f(n-1) = 1*f(n-1) + 0*f(n-2) \\
f(n- 1)=1*f(n-2)+1*f(n-3)\\
f(n-2) = 1*f(n-2) + 0*f(n-3) \\
\end{align}</script><script type="math/tex; mode=display">
\begin{equation}
    \left[
    \begin{array}{c c}
    f(n) & f(n-1) \\
    f(n - 1) & f(n-2)
    \end{array} \right]
    = 
    \left[
    \begin{array}{c c}
    f(n - 1) & f(n-2)\\
    f(n - 2) & f(n - 3)
    \end{array}
    \right]
    \left[
    \begin{array}{c c}
    1 & 1\\
    1& 0
    \end{array}
    \right]
\end{equation}</script><p>根据规律建立递推方程:</p>
<script type="math/tex; mode=display">
\begin{align}
    \left[
    \begin{array}{c c}
    f(n) & f(n-1) \\
    f(n - 1) & f(n-2)
    \end{array} \right]
    &= 
    \left[
    \begin{array}{c c}
    f(2) & f(1)\\
    f(1) & f(0)
    \end{array}
    \right]
    \cdot
    \underbrace{
    \left[
    \begin{array}{c c}
    1 & 1\\
    1& 0
    \end{array}
    \right]
    \cdots
    \left[
    \begin{array}{c c}
    1 & 1\\
    1& 0
    \end{array}
    \right]
    }_{n-2} \\
    &=
    \left[
    \begin{array}{c c}
    1 & 1\\
    1 & 0
    \end{array}
    \right] \cdot
    \left[
    \begin{array}{c c}
    1 & 1\\
    1 & 0
    \end{array}
    \right]^{n-2} \\
    &=
    \left[
    \begin{array}{c c}
    1 & 1\\
    1 & 0
    \end{array}
    \right]^{n-1}
\end{align}</script><p>此时，使用矩阵快速幂可快速求得$\left[\begin{array}{c c}1 &amp; 1\ 1 &amp; 0 \end{array}\right]^{n-1}$的第一行第一列的值，此项就是$f(n)$的值。</p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/cmmdc/p/6936196.html">参考链接</a></p>
<h1 id="双指针"><a href="#双指针" class="headerlink" title="双指针"></a>双指针</h1><p>对于求解递增序列arr中，满足 $arr[i] + arr[j] = M$ 的问题可以采用双指针技巧缩短时间复杂度。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">while</span>(i &lt; j)&#123;</span><br><span class="line">    <span class="keyword">if</span>(a[i] + a[j] == M)&#123;</span><br><span class="line">        cout &lt;&lt; i &lt;&lt;<span class="string">&quot; &quot;</span>&lt;&lt;j&lt;&lt;endl;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(a[i] + a[j] &lt; M)&#123;</span><br><span class="line">        i++;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        j--;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="搜索"><a href="#搜索" class="headerlink" title="搜索"></a>搜索</h1><h2 id="BFS"><a href="#BFS" class="headerlink" title="BFS"></a>BFS</h2><h2 id="DFS"><a href="#DFS" class="headerlink" title="DFS"></a>DFS</h2><h1 id="树"><a href="#树" class="headerlink" title="树"></a>树</h1><h1 id="图"><a href="#图" class="headerlink" title="图"></a>图</h1><h1 id="动态规划"><a href="#动态规划" class="headerlink" title="动态规划"></a>动态规划</h1><h1 id="数论"><a href="#数论" class="headerlink" title="数论"></a>数论</h1><h2 id="公约数与公倍数"><a href="#公约数与公倍数" class="headerlink" title="公约数与公倍数"></a>公约数与公倍数</h2><p>最大公约数：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">gcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> !b?a:<span class="built_in">gcd</span>(b,a%b);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>最小公倍数：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lcm</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (a/<span class="built_in">gcd</span>(a,b))*b;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="分数加减"><a href="#分数加减" class="headerlink" title="分数加减"></a>分数加减</h2><p>约定:</p>
<ul>
<li>分母始终为正</li>
<li>分母不为0</li>
<li>若分子为0，将分母改为1</li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Fraction</span>&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="keyword">int</span> up;<span class="comment">//分子</span></span><br><span class="line">    <span class="keyword">int</span> down;<span class="comment">//分母</span></span><br><span class="line">    <span class="built_in">Fraction</span>()&#123;&#125;</span><br><span class="line"></span><br><span class="line">    <span class="built_in">Fraction</span>(<span class="keyword">int</span> up,<span class="keyword">int</span> down)&#123;</span><br><span class="line">        <span class="keyword">this</span>-&gt;up = up;</span><br><span class="line">        <span class="keyword">this</span>-&gt;down = down;</span><br><span class="line">        <span class="keyword">if</span>(<span class="keyword">this</span>-&gt;down &lt; <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">this</span>-&gt;up = -<span class="keyword">this</span>-&gt;up;</span><br><span class="line">            <span class="keyword">this</span>-&gt;down = -<span class="keyword">this</span>-&gt;down;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(<span class="keyword">this</span>-&gt;up == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">this</span>-&gt;down = <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">int</span> d = <span class="built_in">gcd</span>(<span class="built_in">abs</span>(<span class="keyword">this</span>-&gt;up),<span class="built_in">abs</span>(<span class="keyword">this</span>-&gt;down));</span><br><span class="line">            <span class="keyword">this</span>-&gt;up /= d;</span><br><span class="line">            <span class="keyword">this</span>-&gt;down /= d;</span><br><span class="line">        &#125;</span><br><span class="line">        value = (<span class="keyword">double</span>)up / down;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">gcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> !b?a:<span class="built_in">gcd</span>(b,a%b);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    Fraction <span class="keyword">operator</span>+(Fraction&amp; f)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">Fraction</span>(<span class="keyword">this</span>-&gt;up * f.down + f.up * <span class="keyword">this</span>-&gt;down, <span class="keyword">this</span>-&gt;down * f.down);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    Fraction <span class="keyword">operator</span>-(Fraction&amp; f)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">Fraction</span>(<span class="keyword">this</span>-&gt;up * f.down - f.up*<span class="keyword">this</span>-&gt;down, <span class="keyword">this</span>-&gt;down * f.down);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    Fraction <span class="keyword">operator</span>*(Fraction&amp; f)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">Fraction</span>(<span class="keyword">this</span>-&gt;up * f.up, <span class="keyword">this</span>-&gt;down * f.down);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    Fraction <span class="keyword">operator</span>/(Fraction&amp; f)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">Fraction</span>(<span class="keyword">this</span>-&gt;up * f.down, <span class="keyword">this</span>-&gt;down * f.up);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="keyword">this</span>-&gt;down == <span class="number">1</span>)&#123;</span><br><span class="line">            cout &lt;&lt; <span class="keyword">this</span>-&gt;up &lt;&lt; endl;</span><br><span class="line">        &#125;<span class="keyword">else</span></span><br><span class="line">        &#123;</span><br><span class="line">            cout &lt;&lt; up &lt;&lt;<span class="string">&quot;/&quot;</span>&lt;&lt;down &lt;&lt;endl;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="高精"><a href="#高精" class="headerlink" title="高精"></a>高精</h2><h2 id="素数"><a href="#素数" class="headerlink" title="素数"></a>素数</h2><h2 id="埃拉托斯特尼筛法"><a href="#埃拉托斯特尼筛法" class="headerlink" title="埃拉托斯特尼筛法"></a>埃拉托斯特尼筛法</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//求小于n的所有素数</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Eratosthenes</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">  <span class="keyword">int</span> p = <span class="number">0</span>;</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt;= n; ++i) is_prime[i] = <span class="number">1</span>;</span><br><span class="line">  is_prime[<span class="number">0</span>] = is_prime[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">    <span class="keyword">if</span> (is_prime[i]) &#123;</span><br><span class="line">      prime[p++] = i;  <span class="comment">//将素数i 存入prime数组中</span></span><br><span class="line">      <span class="keyword">if</span> ((<span class="keyword">long</span> <span class="keyword">long</span>)i * i &lt;= n)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i * i; j &lt;= n; j += i)</span><br><span class="line">          <span class="comment">// j = 2 * i已经被2的倍数筛选过了</span></span><br><span class="line">          <span class="comment">// j = 3 * i已经被3的倍数筛选过了</span></span><br><span class="line">          <span class="comment">// ...</span></span><br><span class="line">          <span class="comment">// j = (i-1) * i已经被(i-1)的倍数筛选过了</span></span><br><span class="line">          <span class="comment">//所以应该从j = i*i开始筛选</span></span><br><span class="line">          is_prime[j] = <span class="number">0</span>;  <span class="comment">// 是i的倍数的均不是素数</span></span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> p;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="质因子分解"><a href="#质因子分解" class="headerlink" title="质因子分解"></a>质因子分解</h2><h2 id="大整数运算"><a href="#大整数运算" class="headerlink" title="大整数运算"></a>大整数运算</h2><h2 id="扩展欧几里得算法"><a href="#扩展欧几里得算法" class="headerlink" title="扩展欧几里得算法"></a>扩展欧几里得算法</h2><h2 id="排列组合"><a href="#排列组合" class="headerlink" title="排列组合"></a>排列组合</h2><h2 id="博弈论"><a href="#博弈论" class="headerlink" title="博弈论"></a>博弈论</h2><h1 id="常用模板题"><a href="#常用模板题" class="headerlink" title="常用模板题"></a>常用模板题</h1><h2 id="两日期之间间隔天数"><a href="#两日期之间间隔天数" class="headerlink" title="两日期之间间隔天数 "></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-days-between-two-dates/">两日期之间间隔天数 </a></h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">daysBetweenDates</span><span class="params">(string date1, string date2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> year1,year2,month1,month2,day1,day2;</span><br><span class="line">    <span class="built_in">sscanf</span>(date1.<span class="built_in">c_str</span>(),<span class="string">&quot;%d-%d-%d&quot;</span>,&amp;year1,&amp;month1,&amp;day1);</span><br><span class="line">    <span class="built_in">sscanf</span>(date2.<span class="built_in">c_str</span>(),<span class="string">&quot;%d-%d-%d&quot;</span>,&amp;year2,&amp;month2,&amp;day2);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">fabs</span>(<span class="built_in">myDate</span>(year1,month1,day1)-<span class="built_in">myDate</span>(year2,month2,day2));</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    cout &lt;&lt; <span class="built_in">daysBetweenDates</span>(<span class="string">&quot;2019-06-29&quot;</span>,<span class="string">&quot;2019-06-30&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">solution <span class="number">1</span>:</span><br><span class="line"> <span class="function"><span class="keyword">int</span> <span class="title">myDate</span><span class="params">(<span class="keyword">int</span> year, <span class="keyword">int</span> month, <span class="keyword">int</span> day)</span> </span></span><br><span class="line"><span class="function"> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (month &lt; <span class="number">3</span>)&#123;</span><br><span class="line">        year--;</span><br><span class="line">        month += <span class="number">12</span>;</span><br><span class="line">    &#125;</span><br><span class="line">       </span><br><span class="line">    <span class="keyword">return</span> <span class="number">365</span> * year + year / <span class="number">4</span> - year / <span class="number">100</span> + year / <span class="number">400</span> + (<span class="number">153</span> * month - <span class="number">457</span>) / <span class="number">5</span> + day - <span class="number">306</span>;</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">solution <span class="number">2</span>:</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isLeap</span><span class="params">(<span class="keyword">int</span> year)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>((year % <span class="number">4</span> == <span class="number">0</span> &amp;&amp; year % <span class="number">100</span> != <span class="number">0</span>) || year % <span class="number">400</span> == <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">f</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(x == <span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(x == <span class="number">2</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">3</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(x &gt;= <span class="number">3</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">13</span>*(x+<span class="number">1</span>)/<span class="number">5</span><span class="number">-7</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">myDate</span><span class="params">(<span class="keyword">int</span> year,<span class="keyword">int</span> month,<span class="keyword">int</span> day)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> m = (<span class="built_in">isLeap</span>(year) &amp;&amp; month &lt;= <span class="number">2</span>)?<span class="built_in">f</span>(month)<span class="number">-1</span>:<span class="built_in">f</span>(month);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">365</span>*(year - <span class="number">1</span>) + year / <span class="number">4</span> - year / <span class="number">100</span> + year / <span class="number">400</span> + <span class="number">28</span>*(month - <span class="number">1</span>) + m +day;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">solution <span class="number">3</span>:</span><br><span class="line"><span class="keyword">int</span> f[] = &#123;<span class="number">0</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">6</span>,<span class="number">8</span>,<span class="number">11</span>,<span class="number">13</span>,<span class="number">16</span>,<span class="number">19</span>,<span class="number">21</span>,<span class="number">24</span>,<span class="number">26</span>&#125;;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">myDate</span><span class="params">(<span class="keyword">int</span> year,<span class="keyword">int</span> month,<span class="keyword">int</span> day)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> m = (<span class="built_in">isLeap</span>(year) &amp;&amp; month &lt;= <span class="number">2</span>)?f[month]<span class="number">-1</span>:f[month];</span><br><span class="line">    <span class="keyword">return</span> <span class="number">365</span>*(year - <span class="number">1</span>) + year / <span class="number">4</span> - year / <span class="number">100</span> + year / <span class="number">400</span> + <span class="number">28</span>*(month - <span class="number">1</span>) + m +day;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">solution <span class="number">4</span>:</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">myDate</span><span class="params">(<span class="keyword">int</span> year,<span class="keyword">int</span> month,<span class="keyword">int</span> day)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(month &lt; <span class="number">3</span>)&#123;</span><br><span class="line">        year--;</span><br><span class="line">        month += <span class="number">12</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">365</span>*(year - <span class="number">1</span>) + year / <span class="number">4</span> - year / <span class="number">100</span> + year / <span class="number">400</span> + <span class="number">28</span>*(month - <span class="number">1</span>) + <span class="number">13</span>*(month+<span class="number">1</span>)/<span class="number">5</span><span class="number">-7</span> +day;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="拼数"><a href="#拼数" class="headerlink" title="拼数"></a><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1012">拼数</a></h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">string result[<span class="number">20</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">comp</span><span class="params">(string a,string b)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> a+b&gt;b+a;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	cin&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; n;i++)&#123;</span><br><span class="line">		cin&gt;&gt;result[i];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">sort</span>(result,result+n,comp);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt;n;i++)&#123;</span><br><span class="line">		cout&lt;&lt;result[i];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="进制转换"><a href="#进制转换" class="headerlink" title="进制转换"></a>进制转换</h2><blockquote>
<p>除基取余法</p>
</blockquote>
<p>将N进制数<code>x</code>转换为十进制数<code>y</code>：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//x为整数</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">convertNto10</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> N)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> y = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> base = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(x != <span class="number">0</span>)&#123;</span><br><span class="line">        y += (x % <span class="number">10</span>)*base;</span><br><span class="line">        x = x / <span class="number">10</span>;</span><br><span class="line">        base = base * N;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> y;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//x为字符串</span></span><br><span class="line"><span class="function"><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="title">convertNto10</span><span class="params">(string x,<span class="keyword">int</span> N)</span></span>&#123;</span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> base = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> y = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = x.<span class="built_in">length</span>() - <span class="number">1</span>;i &gt;= <span class="number">0</span>;i--)&#123;</span><br><span class="line">        y += (x[i] &gt;= <span class="string">&#x27;A&#x27;</span> &amp;&amp; x[i] &lt;= <span class="string">&#x27;Z&#x27;</span>)?((x[i]-<span class="string">&#x27;A&#x27;</span> + <span class="number">10</span>)*base):((x[i] - <span class="string">&#x27;0&#x27;</span>)*base);</span><br><span class="line">        base *= N;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> y;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>将十进制<code>x</code>转换为N进制数<code>y</code> (所支持转换的十进制数   $0 \leq x \leq 2^{64} - 1$):</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">string <span class="title">convert10toN</span><span class="params">(<span class="keyword">unsigned</span>  <span class="keyword">long</span> <span class="keyword">long</span> x,<span class="keyword">int</span> N)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = <span class="number">19</span>;</span><br><span class="line">    <span class="keyword">char</span> arr[length];</span><br><span class="line">    <span class="keyword">int</span> i = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(x != <span class="number">0</span>)&#123;</span><br><span class="line">        arr[i++] = ((x % N)&gt;<span class="number">9</span>)? ((x % N) - <span class="number">10</span> + <span class="string">&#x27;A&#x27;</span>):((x % N) + <span class="string">&#x27;0&#x27;</span>);</span><br><span class="line">        x /= N;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function">string <span class="title">y</span><span class="params">(arr)</span></span>;</span><br><span class="line">    <span class="built_in">reverse</span>(y.<span class="built_in">begin</span>(),y.<span class="built_in">end</span>());</span><br><span class="line">    <span class="keyword">return</span> y;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>任意进制N，P之间的转换$(1 \leq N,P \leq 36)$:</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">string <span class="title">convertNtoP</span><span class="params">(string num,<span class="keyword">int</span> N,<span class="keyword">int</span> P)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">convert10toN</span>(<span class="built_in">convertNto10</span>(num,N),P);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="回文串判断"><a href="#回文串判断" class="headerlink" title="回文串判断"></a>回文串判断</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isPalindrome</span><span class="params">(string s)</span></span>&#123;</span><br><span class="line">   string t = s;</span><br><span class="line">   <span class="built_in">reverse</span>(t.<span class="built_in">begin</span>(),t.<span class="built_in">end</span>());</span><br><span class="line">   <span class="keyword">return</span> t == s;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isPalindrome</span><span class="params">(string s)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = s.<span class="built_in">length</span>();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; length/<span class="number">2</span>;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(s[i] != s[length-i<span class="number">-1</span>])&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">Author: </span><span class="post-copyright-info"><a href="mailto:undefined">dreamcatcherdeng</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">Link: </span><span class="post-copyright-info"><a href="https://dreamcatcherdeng.github.io/personal-blog/2022/07/13/Algorithm/">https://dreamcatcherdeng.github.io/personal-blog/2022/07/13/Algorithm/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">Copyright Notice: </span><span class="post-copyright-info">All articles in this blog are licensed under <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a> unless stating additionally.</span></div></div><div class="tag_share"><div class="post-meta__tag-list"></div><div class="post_share"><div class="social-share" data-image="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-e7ek7k.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-full"><a href="/personal-blog/2022/07/13/Activity/"><img class="prev-cover" src="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-72rd8e.jpg" onerror="onerror=null;src='/personal-blog/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">Previous Post</div><div class="prev_info">Activity</div></div></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://n.sinaimg.cn/sinakd10100/452/w1080h972/20200416/93dc-iskepxs3894040.jpg" onerror="this.onerror=null;this.src='/personal-blog/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">dreamcatcherdeng</div><div class="author-info__description"></div></div><div class="card-info-data is-center"><div class="card-info-data-item"><a href="/personal-blog/archives/"><div class="headline">Articles</div><div class="length-num">34</div></a></div><div class="card-info-data-item"><a href="/personal-blog/tags/"><div class="headline">Tags</div><div class="length-num">0</div></a></div><div class="card-info-data-item"><a href="/personal-blog/categories/"><div class="headline">Categories</div><div class="length-num">35</div></a></div></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/xxxxxx"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/DreamcatcherDENG" target="_blank" title="Github"><i class="fab fa-github"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>Announcement</span></div><div class="announcement_content">This is my Blog</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>Catalog</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B"><span class="toc-number">1.</span> <span class="toc-text">数据类型</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%A6%E5%8F%B7%E5%AE%9A%E4%B9%89"><span class="toc-number">2.</span> <span class="toc-text">符号定义</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%87%BD%E6%95%B0%E5%AE%9A%E4%B9%89"><span class="toc-number">3.</span> <span class="toc-text">函数定义</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%B5%AE%E7%82%B9%E6%95%B0%E7%9A%84%E6%AF%94%E8%BE%83"><span class="toc-number">3.1.</span> <span class="toc-text">浮点数的比较</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%8E%B7%E5%8F%96%E6%95%B0%E7%BB%84%E7%9A%84%E9%95%BF%E5%BA%A6"><span class="toc-number">3.2.</span> <span class="toc-text">获取数组的长度</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F"><span class="toc-number">4.</span> <span class="toc-text">排序</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F"><span class="toc-number">4.1.</span> <span class="toc-text">冒泡排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%80%E5%8D%95%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F"><span class="toc-number">4.2.</span> <span class="toc-text">简单选择排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F"><span class="toc-number">4.3.</span> <span class="toc-text">插入排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">4.4.</span> <span class="toc-text">归并排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-number">4.5.</span> <span class="toc-text">快速排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="toc-number">4.6.</span> <span class="toc-text">堆排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A1%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">4.7.</span> <span class="toc-text">桶排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F"><span class="toc-number">4.8.</span> <span class="toc-text">基数排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F"><span class="toc-number">4.9.</span> <span class="toc-text">计数排序</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E9%80%92%E5%BD%92"><span class="toc-number">5.</span> <span class="toc-text">递归</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E8%B4%AA%E5%BF%83"><span class="toc-number">6.</span> <span class="toc-text">贪心</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%B3%95"><span class="toc-number">7.</span> <span class="toc-text">二分法</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE"><span class="toc-number">7.1.</span> <span class="toc-text">二分查找</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%B3%95%E6%B1%82%E8%BF%91%E4%BC%BC%E5%80%BC"><span class="toc-number">7.2.</span> <span class="toc-text">二分法求近似值</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%BF%AB%E9%80%9F%E5%B9%82"><span class="toc-number">8.</span> <span class="toc-text">快速幂</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B4%E6%95%B0%E5%BF%AB%E9%80%9F%E5%B9%82"><span class="toc-number">8.1.</span> <span class="toc-text">整数快速幂</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%9F%A9%E9%98%B5"><span class="toc-number">9.</span> <span class="toc-text">矩阵</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82"><span class="toc-number">10.</span> <span class="toc-text">矩阵快速幂</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8F%8C%E6%8C%87%E9%92%88"><span class="toc-number">11.</span> <span class="toc-text">双指针</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%90%9C%E7%B4%A2"><span class="toc-number">12.</span> <span class="toc-text">搜索</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#BFS"><span class="toc-number">12.1.</span> <span class="toc-text">BFS</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#DFS"><span class="toc-number">12.2.</span> <span class="toc-text">DFS</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%A0%91"><span class="toc-number">13.</span> <span class="toc-text">树</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%9B%BE"><span class="toc-number">14.</span> <span class="toc-text">图</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="toc-number">15.</span> <span class="toc-text">动态规划</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E8%AE%BA"><span class="toc-number">16.</span> <span class="toc-text">数论</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%85%AC%E7%BA%A6%E6%95%B0%E4%B8%8E%E5%85%AC%E5%80%8D%E6%95%B0"><span class="toc-number">16.1.</span> <span class="toc-text">公约数与公倍数</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%88%86%E6%95%B0%E5%8A%A0%E5%87%8F"><span class="toc-number">16.2.</span> <span class="toc-text">分数加减</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%AB%98%E7%B2%BE"><span class="toc-number">16.3.</span> <span class="toc-text">高精</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%B4%A0%E6%95%B0"><span class="toc-number">16.4.</span> <span class="toc-text">素数</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95"><span class="toc-number">16.5.</span> <span class="toc-text">埃拉托斯特尼筛法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%B4%A8%E5%9B%A0%E5%AD%90%E5%88%86%E8%A7%A3"><span class="toc-number">16.6.</span> <span class="toc-text">质因子分解</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%A7%E6%95%B4%E6%95%B0%E8%BF%90%E7%AE%97"><span class="toc-number">16.7.</span> <span class="toc-text">大整数运算</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95"><span class="toc-number">16.8.</span> <span class="toc-text">扩展欧几里得算法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8E%92%E5%88%97%E7%BB%84%E5%90%88"><span class="toc-number">16.9.</span> <span class="toc-text">排列组合</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8D%9A%E5%BC%88%E8%AE%BA"><span class="toc-number">16.10.</span> <span class="toc-text">博弈论</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%B8%B8%E7%94%A8%E6%A8%A1%E6%9D%BF%E9%A2%98"><span class="toc-number">17.</span> <span class="toc-text">常用模板题</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%A4%E6%97%A5%E6%9C%9F%E4%B9%8B%E9%97%B4%E9%97%B4%E9%9A%94%E5%A4%A9%E6%95%B0"><span class="toc-number">17.1.</span> <span class="toc-text">两日期之间间隔天数 </span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8B%BC%E6%95%B0"><span class="toc-number">17.2.</span> <span class="toc-text">拼数</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%BF%9B%E5%88%B6%E8%BD%AC%E6%8D%A2"><span class="toc-number">17.3.</span> <span class="toc-text">进制转换</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9B%9E%E6%96%87%E4%B8%B2%E5%88%A4%E6%96%AD"><span class="toc-number">17.4.</span> <span class="toc-text">回文串判断</span></a></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>Recent Post</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/personal-blog/2022/07/13/RegularExpression/" title="正则表达式"><img src="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/romance-2258599_960_720.jpg" onerror="this.onerror=null;this.src='/personal-blog/img/404.jpg'" alt="正则表达式"/></a><div class="content"><a class="title" href="/personal-blog/2022/07/13/RegularExpression/" title="正则表达式">正则表达式</a><time datetime="2022-07-13T09:38:01.002Z" title="Created 2022-07-13 17:38:01">2022-07-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/personal-blog/2022/07/13/Nodejs/" title="JavaScript and NodeJs"><img src="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-0qxx54.jpg" onerror="this.onerror=null;this.src='/personal-blog/img/404.jpg'" alt="JavaScript and NodeJs"/></a><div class="content"><a class="title" href="/personal-blog/2022/07/13/Nodejs/" title="JavaScript and NodeJs">JavaScript and NodeJs</a><time datetime="2022-07-13T09:38:00.960Z" title="Created 2022-07-13 17:38:00">2022-07-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/personal-blog/2022/07/13/MySQL/" title="MySQL"><img src="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-e7ek7k.jpg" onerror="this.onerror=null;this.src='/personal-blog/img/404.jpg'" alt="MySQL"/></a><div class="content"><a class="title" href="/personal-blog/2022/07/13/MySQL/" title="MySQL">MySQL</a><time datetime="2022-07-13T09:38:00.957Z" title="Created 2022-07-13 17:38:00">2022-07-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/personal-blog/2022/07/13/JAVA/" title="JAVA"><img src="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-72rd8e.jpg" onerror="this.onerror=null;this.src='/personal-blog/img/404.jpg'" alt="JAVA"/></a><div class="content"><a class="title" href="/personal-blog/2022/07/13/JAVA/" title="JAVA">JAVA</a><time datetime="2022-07-13T09:38:00.948Z" title="Created 2022-07-13 17:38:00">2022-07-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/personal-blog/2022/07/13/ViewPager/" title="ViewPager"><img src="https://gitee.com/DreamcatcherDENG/drawing-bed/raw/master/img/wallhaven-0qxx54.jpg" onerror="this.onerror=null;this.src='/personal-blog/img/404.jpg'" alt="ViewPager"/></a><div class="content"><a class="title" href="/personal-blog/2022/07/13/ViewPager/" title="ViewPager">ViewPager</a><time datetime="2022-07-13T09:38:00.929Z" title="Created 2022-07-13 17:38:00">2022-07-13</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2022 By dreamcatcherdeng</div><div class="framework-info"><span>Framework </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>Theme </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="Read Mode"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="Toggle Between Light And Dark Mode"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="Toggle between single-column and double-column"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="Setting"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="Table Of Contents"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="Back To Top"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">Local search</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span>  Loading the Database</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="Search for Posts" type="text"/></div></div><hr/><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="/personal-blog/js/utils.js"></script><script src="/personal-blog/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.js"></script><script src="/personal-blog/js/search/local-search.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
  window.MathJax = {
    tex: {
      inlineMath: [ ['$','$'], ["\\(","\\)"]],
      tags: 'ams'
    },
    chtml: {
      scale: 1.2
    },
    options: {
      renderActions: {
        findScript: [10, doc => {
          for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
            const display = !!node.type.match(/; *mode=display/)
            const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
            const text = document.createTextNode('')
            node.parentNode.replaceChild(text, node)
            math.start = {node: text, delim: '', n: 0}
            math.end = {node: text, delim: '', n: 0}
            doc.math.push(math)
          }
        }, ''],
        insertScript: [200, () => {
          document.querySelectorAll('mjx-container:not\([display]\)').forEach(node => {
            const target = node.parentNode
            if (target.nodeName.toLowerCase() === 'li') {
              target.parentNode.classList.add('has-jax')
            } else {
              target.classList.add('has-jax')
            }
          });
        }, '', false]
      }
    }
  }
  
  const script = document.createElement('script')
  script.src = 'https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js'
  script.id = 'MathJax-script'
  script.async = true
  document.head.appendChild(script)
} else {
  MathJax.startup.document.state(0)
  MathJax.texReset()
  MathJax.typeset()
}</script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/katex@latest/dist/katex.min.css"><script src="https://cdn.jsdelivr.net/npm/katex@latest/dist/contrib/copy-tex.min.js"></script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/katex@latest/dist/contrib/copy-tex.css"><script>(() => {
  document.querySelectorAll('#article-container span.katex-display').forEach(item => {
    btf.wrap(item, 'div', { class: 'katex-wrap'})
  })
})()</script></div><canvas class="fireworks" mobile="false"></canvas><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/fireworks.min.js"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><script src="/personal-blog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginModelPath":"assets/","model":{"jsonPath":"/personal-blog/live2dw/assets/shizuku.model.json"},"display":{"position":"left","width":250,"height":300,"hOffset":0,"vOffset":0,"opacity":0.1},"mobile":{"show":false},"log":false,"pluginJsPath":"lib/","pluginRootPath":"live2dw/","tagMode":false});</script></body></html>